/**
 * @author: li_jian
 * @version: 1.0
 * @date: 2020/7/13 07:06
 * @description： @link{https://www.nowcoder.com/practice/9f3231a991af4f55b95579b44b7a01ba?tpId=13&&tqId=11159&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking}
 */
public class JZ6_旋转数组的最小数字 {

    public int minNumberInRotateArray(int[] array) {
        if (array.length == 0)
            return 0;

        int l = 0, h = array.length - 1;
        while (l < h) {
            int m = (l + h) / 2;
            if (array[l] == array[m] && array[m] == array[h]) {
                return minNumber(array, l, h);
            } else if (array[m] <= array[h]) {
                h = m;
            } else {
                l = m + 1;
            }
        }
        return array[l];
    }

    /**
     * 如果数组元素允许重复，会出现一个特殊的情况：nums[l] == nums[m] == nums[h]，此时无法确定解在哪个区间，需要切换到顺序查找
     *
     * @param array
     * @param l
     * @param h
     * @return
     */
    public int minNumber(int[] array, int l, int h) {
        for (int i = l; i < h; i++) {
            if (array[i] < array[i + 1])
                return array[i];
        }
        return array[l];
    }
}
